package Graph;

import java.util.Arrays;
import java.util.LinkedList;

public class EcerciseTest {
    private int vetexlenth;
    private int edgesNum;
    private char [] vretexs;
    private int[][] edgesWeight;
    private boolean [] isVisited;
    public static void main(String[] args) {

        char[] vertex = new char[]{'A','B','C','D','E','F','G'};//0-5
        int n = vertex.length;
        EcerciseTest exercise = new EcerciseTest(n,vertex);
        //1表示连起来 0表示不连起来
        exercise.addEdge(0,1,7);
        exercise.addEdge(0,5,13);
        exercise.addEdge(0,6,6);
        exercise.addEdge(1,0,7);
        exercise.addEdge(1,2,12);
        exercise.addEdge(1,6,4);
        exercise.addEdge(2,1,12);
        exercise.addEdge(2,3,5);
        exercise.addEdge(2,6,19);
        exercise.addEdge(3,2,5);
        exercise.addEdge(3,4,11);
        exercise.addEdge(3,6,20);
        exercise.addEdge(4,3,11);
        exercise.addEdge(4,5,10);
        exercise.addEdge(4,6,16);
        exercise.addEdge(5,0,13);
        exercise.addEdge(5,4,10);
        exercise.addEdge(5,6,16);
        exercise.showGraph();
        System.out.print("深度遍历:");
        exercise.showGraphOfdfn();
        System.out.println();
        System.out.print("广度遍历:");
        exercise.showGraphOfBfs();
    }
    public EcerciseTest(int n,char[]vretexs){
        this.vetexlenth=n;
        this.vretexs=vretexs;
        edgesWeight = new int[n][n];
    }
    public void addEdge(int v1,int v2,int weight){
        edgesWeight[v1][v2]=weight;
        edgesWeight[v2][v1]=weight;
        edgesNum++;
    }
    public void showGraph(){
        for (int [] item:
             edgesWeight) {
            System.out.println(Arrays.toString(item));
        }
    }
    //深度优先
    public int firstIndex(int index){
        for (int i = 0 ; i < vetexlenth ; i++){
            if (edgesWeight[index][i]>0){
                return i;
            }
        }
        return -1;
    }
    public int getNextIndex(int v1,int v2){
        for (int i = v2+1 ; i<vetexlenth ; i++){
            if(edgesWeight[v1][i]>0){
                return i;
            }
        }
        return -1;
    }
    private void showGraphOfdfn(boolean [] isVisited,int i){
        System.out.print(vretexs[i]);
        isVisited[i]=true;
        int w = firstIndex(i);
        while (w!=-1){
            if(!isVisited[w]){
                showGraphOfdfn(isVisited,w);
            }
            w = getNextIndex(i,w);
        }
    }
    public void showGraphOfdfn(){
        isVisited = new boolean[vetexlenth];
        for (int i = 0 ; i < vetexlenth ; i++){
            if(!isVisited[i]){
                showGraphOfdfn(isVisited,i);
            }
        }
    }
    private void showGraphOfBfs(boolean [] isVisited,int i ){
        int temp;
        int w;
        //创建队列
        LinkedList linkedList = new LinkedList();
        System.out.print(vretexs[i]);
        isVisited[i]=true;
        linkedList.addFirst(i);
        //队列，当队列不为空时，方法继续，否则结束方法
        while (!linkedList.isEmpty()){
            temp = (int) linkedList.removeFirst();
            w=firstIndex(temp);
            while (w!=-1){
                if(!isVisited[w]){
                    System.out.print(vretexs[w]);
                    linkedList.addLast(w);
                    isVisited[w]=true;
                }
                w=getNextIndex(temp,w);
            }
        }
    }
    public void showGraphOfBfs(){
        isVisited = new boolean[vetexlenth];
        for (int i = 0; i < vetexlenth; i++) {
            if(!isVisited[i]){
                showGraphOfBfs(isVisited,i);
            }
        }
    }
}
